package skipList_01;

import java.security.acl.NotOwnerException;

/**
 * @author Tobias Hardes Jul 28, 2014 10:37:08 PM
 */
public class SkipList {
	private SkipListNode header;
	private int infinity;
	private SkipListNode bottom = null;
	private SkipListNode tail = null;

	public SkipList(int inf) {
		this.infinity = inf;
		bottom = new SkipListNode(0);
		bottom.setDown(bottom);
		bottom.setRight(bottom.getDown());

		bottom.setLevel(0);

		tail = new SkipListNode(this.infinity);
		tail.setRight(tail);

		tail.setLevel(0);

		header = new SkipListNode(infinity, tail, bottom, 0); // First rows
																// header
	}

	public void insert(int x) {
		SkipListNode current = header;
		bottom.setElement(x);
		while (current != bottom) {
			while (current.getElement() < x)
				current = current.getRight(); // Move to the right
			/*
			 * If gap size is 3 or at bottom level and must insert, then promote
			 * middle element
			 */
			if (current.getDown().getRight().getRight().getElement() < current
					.getElement()) {

				current.setRight(new SkipListNode(current.getElement(), current
						.getRight(), current.getDown().getRight().getRight(),
						current.getLevel()));
				current.setElement(current.getDown().getRight().getElement());
			} else
				current = current.getDown();
		}

		/* Raise height of skiplist if necessary */
		if (header.getRight() != tail)
			header = new SkipListNode(infinity, tail, header,
					header.getLevel() + 1);

	}

	public void printList() {
		// System.out.print("\nSkiplist = ");
		SkipListNode current = header;
		while (current.getDown() != bottom)
			current = current.getDown();

		while (current.getRight() != tail) {
			System.out.print(current.getElement() + " ");
			current = current.getRight();
		}
		System.out.println();
	}

	public void delete(int x) {
		// TODO Auto-generated method stub
		throw new UnsupportedOperationException();

	}

	private int randheight() {
		/* liefert eine zuf"allige H"ohe zwischen 0 und maxHeight */
		int height = 0;
		while (general_algorithms.RandomNumber.randint() % 2 == 1) {
			height++;
		}
		return height;
	}

	public void search(int x) {
		SkipListNode current = header;
		bottom.setElement(x);
		while (current != bottom) {
			while (current.getElement() < x)
				current = current.getRight(); // Move to the right
			/*
			 * If gap size is 3 or at bottom level and must insert, then promote
			 * middle element
			 */
			if (current.getDown().getRight().getRight().getElement() < current
					.getElement()) {
				current.setRight(new SkipListNode(current.getElement(), current
						.getRight(), current.getDown().getRight().getRight(),
						current.getLevel()));
				current.setElement(current.getDown().getRight().getElement());
			} else
				current = current.getDown();
		}

	}
}
